//数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，
//等等。
//
// 请写一个函数，求任意第n位对应的数字。
//
//
//
// 示例 1：
//
// 输入：n = 3
//输出：3
//
//
// 示例 2：
//
// 输入：n = 11
//输出：0
//
//
//
// 限制：
//
//
// 0 <= n < 2^31
//
//
// 注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/
//
// Related Topics 数学 二分查找 👍 341 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function findNthDigit(n: number): number {
    //? 0   9 * 0
    //? 1-9 9 * 1
    //? 10-99 90 * 2
    //? 100-999 900 * 3
    //? ....    9000 * 4
    //? cur记录位数 base记录位数对应的个数
    let cur = 1, base = 9;
    //?  找到他是x位数中的第n位
    while(n > cur * base){
        n -= cur * base;
        cur++;
        base*=10;
        if(Number.MAX_SAFE_INTEGER / base < cur){
            break;
        }
    }
    //? 转换为0开始的坐标
    n--;
    //? 拿到这个数num idx是第几位数
    const num = Math.pow(10,cur - 1) + Math.floor(n / cur), idx = n % cur;
    //? 通过求余拿到某一位的数
    return Math.floor(num / Math.pow(10,cur - 1 - idx)) % 10;
};
//leetcode submit region end(Prohibit modification and deletion)
